package LC;

/**
 * https://leetcode.com/problems/scramble-string/description/
 * Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
 * Below is one possible representation of s1 = "great":
 * To scramble the string, we may choose any non-leaf node and swap its two children.
 * For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
 * We say that "rgeat" is a scrambled string of "great".
 * Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
 * We say that "rgtae" is a scrambled string of "great".
 * Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
 * 字符串树形颠倒匹配
 */
public class LC_087_ScrambleString_Recur_BackTracking {
    public static void main(String[] args) {
        String s1 = "great";
        String s2 = "rgeat";
        boolean f = Solution.isScramble(s1, s2);
        System.out.println(f);
    }

    static class Solution {
        static boolean isScramble(String s1, String s2) {
            char[] a1 = s1.toCharArray();
            char[] a2 = s2.toCharArray();
            return isScramble(a1, 0, a1.length - 1, a2, 0, a2.length - 1);
        }

        private static boolean isScramble(char[] a1, int start1, int end1, char[] a2, int start2, int end2) {
            int[] letters = new int[26];
            boolean isSame = true;
            for (int i = start1, j = start2; i <= end1; i++, j++) {
                letters[a1[i] - 'a']++;
                letters[a2[j] - 'a']--;
                isSame = isSame && a1[i] == a2[j];
            }

            if (isSame) return true;
            for (int i = 0; i < 26; i++) if (letters[i] != 0) return false;
            for (int i = start1, j = start2; i < end1; i++, j++) {
                if (isScramble(a1, start1, i, a2, start2, j) && isScramble(a1, i + 1, end1, a2, j + 1, end2))
                    return true;
                if (isScramble(a1, start1, i, a2, end2 - j + start2, end2) && isScramble(a1, i + 1, end1, a2, start2, end2 - j + start2 - 1))
                    return true;
            }
            return false;
        }
    }
}
